{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 随机梯度下降法\n",
    "## 梯度下降法的缺点\n",
    "+ 从上一节推导出的下面的表达式可知，每一个样本都参与了运算，这使得当样本数较大时，计算梯度也会很慢，这种方法叫做`批量梯度下降法`\n",
    "+ 为了解决样本数量影响训练时间的问题，有了本节的`随机梯度下降法`\n",
    "![最终的损失函数J的导数dJ的向量化表示](../05-Vectorize-Gradient-Descent/images/最终的损失函数J的导数dJ的向量化表示.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 100000\n",
    "\n",
    "x = np.random.normal(size=m)\n",
    "X = x.reshape(-1,1)\n",
    "y = 4.*x + 3. + np.random.normal(0, 3, size=m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXkAAAD4CAYAAAAJmJb0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3dbXBc53Uf8P/B8lJeyK0WjBDHXBEkR9WQEc2QqDAyJ/jQkI5FJbIlRIpMK2LG02ZG0xlnGqoOWzBWbTKVRpjBOHSmTaajpp04I9WGZNFrqoyHSkS2maFDxaAXFAOLbCVLprRUY6Tiug65IhfA6Qfggrt379vufd29/9+MRsC+3YtL4Oyz5znPeURVQUREvakv6RMgIqLoMMgTEfUwBnkioh7GIE9E1MMY5ImIetiqpE+g0a233qobNmxI+jSIiLrKmTNn/l5VB+3uS1WQ37BhA6anp5M+DSKiriIiP3K6j+kaIqIexiBPRNTDGOSJiHoYgzwRUQ9jkCci6mGpqq4hIsqCUrmCyeMXcKlaw9pCHvt3b8LYcDGSYzHIExHFqFSu4MCRc6jVFwAAlWoNB46cA4BIAj2DPBFRBJxG65PHL6wEeFOtvoDJ4xcY5ImIuoHbaP1StWb7HKfbg+LEKxFRyNxG62sLedvnON0eFIM8EfWsUrmC0YkT2Dh+DKMTJ1AqV2I5rttoff/uTcgbuabb80YO+3dviuRcmK4hop4U9wRno7WFPCo2gX5tIb9ybFbXEBEFEPcEZ6P9uzc1vcEAzaP1seFi5OdgYpAnoq7Qbm153BOcjeIerbthkCei1Osk9eKWMvFzvKABOs7RuhsGeSJKvU5SL14pk0aNQf2WvIEr1+dRX1AA7efy41zN6geDPFGGpC0AWdmdHwDbETngnnrxmzKxfkqo1uotr+U3l+/1iSOJ688gT5QRSVab+FEqV7D/hbOoL94YQe+bmnF9jlfqxU/KxO5Tgh0/uXy3TxwAErn+rJMnygivAJS0g0dnVwK8X1euzQeuffc7Edv4huJUf+822ZvU9edInigjkqw28cMuTeLnOe2Ohq0pk1vyhuexG3P5bp+I3CZ7k7r+HMkTZUTcy+n9aBwRd6pxNFwqVzD8+y9jw/gxbBg/hu2HXm4a6ZsBulKtQbEUoK9cn4fRJ02vafQJBvoNCIBiIY+nH9zalON3GpG7rWZN6vpzJE+UEe1Um8TBOiIO4lK1tpTT/+bZlaoYYGmkv29qBvumZlAs5HHl2nzL8eoLioF+A/2rVzlOiJbKFWw/9LLriP9SteY52Ws9PyMnkV9/BnmijEjTAh3zPMII8MDSaHjy+IWmAGrlVKEDANWrdZS/dE/TbWZax+151nPwrJ6xnl57UxAdCRzkRWQdgD8D8HMAFgE8o6p/KCJrAEwB2ADgbQCfUdXLQY9HRJ1LywIdILxctMA9gPthTZm0+ykjb+Swc/Oga/XM5PELLRPL9UWNvM1CGDn5eQBfUNWfB7ADwOdF5E4A4wBeUdU7ALyy/D0REYDwctFBB8MCYOfmwabb2vmUYebsT56fc62e6dqJV1V9T1W/v/z1TwG8DqAI4AEAX1t+2NcAjAU9FhF1F7dWv3aTlHG4eXXzMRXAs6cvYkPDOfoNvMVCHqfGd2FsuOj4nMryfIHTm9oteaOt829XqNU1IrIBwDCAVwF8RFXfA5beCAD8rMNzHhORaRGZnpubC/N0iKgD7fZgd3r8o//5r7FvaqapkuXAkXMr948NF/H0g1sh4vLiIRMAqu55+wNHzvkOvFev36jTd/tkcuDIOezcPNhSxQMAV64Hr/V3I24/cFsvJPJhAP8TwFOqekREqqpaaLj/sqoOuL3GyMiITk9Ph3I+RNQ+u1x03sg1lRD6efw/HboFp9583/YY5ujX9ETpHJ49fTHEn8KZ0QfUF70fN9Bv4IP6oq+UjXl9ALjm8YuFPK5en8flq60VOtZr0i4ROaOqI3b3hTKSFxEDwIsAnlPVI8s3/52IfHT5/o8C+HEYxyKi6DjVgB96abatxzsFeOBG+gJYCvDPxRTgAX8BHliqtnn6wa0oFvIQAIW8ASNn/5Gjsa+NGeztXKrWULUJ8OZ9UQkc5EVEAPwXAK+r6h803HUUwOeWv/4cgG8HPRYRRcsp2Fy+Wsf2Qy+3pGQ6rWr511MzuPPffQfPnr4YRxVhx06N78JbE/fh5ptWuZZnmtdtbLiIosuipyQWRIUxkh8F8JsAdonIzPJ/vwpgAsAnReR/A/jk8vdElGJuwaZaqzfl1p8onev4OIsArvodVidAAeybmllZMev1ZtZ43ZwmlK9en8fOzYOx7u8KhJiTDwNz8kTh6aStbalc8ez8aBLEspYncUafuDZOM/oEkw9va1khe/DobMsK2byRw0N3FXHy/FyoC9LccvJc8UrUg9yaaAHOq17Hhos4cOQ11HyMsrMQ4AF4d8a0SdWbi5+sQb5WX8Cx195D/+r4Qi+DPFEPcpoQPXh0FtfmFx2D/8Gjs74CPN1QX7Bfteo2v2FW2MTRU55BnqgHOQUYp12PDr0067tkkFrZXW+ntsNWtfoC9k3NrHSxDDvYs9UwUQ9qt1rj8tU6A3wAdte73RW91sViYWGQJ0q5dlegAsm1DMgip+oYs27erLUvFvIoeKykjWKnKAZ5ohSz2+TCz2hvbLiIh+7y/7E/xs4CPcdtNbB1gvvg/Vs833zDXhjFIE+UYkH2BT322nu+j6MAbNqqkIecQ+MdpzdnACujeydhL4zixCtRCjjVtLfTntb6GnY9Uty0uYc2AVhQta2OcXtzNrtWOvX9CXthFIM8UcI63Rja6zUoHrX6An7vyGtNQd7Pm3NcO3UxyBMlzGtjaLvOhpVqDRvGj62sOs2JYCFFq9ez5mp9EU+UzuHJsaUGZX7fnOPYqYtBnihm1rSK06jbujG03ePMsM4An7xnT1/EyPo1GBsupmrTdAZ5ohjZpVWcesBYN4bmaD39rPn5xjfznZsHMXn8Ah6fmkGh34Aq8JNaPfIN1dmgjChGoxMnbEfk1kBvNrJ68UyFi5S6jN0GIF4bg7ttzOJH5JuGEJE/ThNyCqyU1eVEUKsv4OuvvsMA34Xs/o29NgaPYhGUiUGeKEZONdA5kZXUjZmSYWqmO9n9G/tZ4BTV7lAM8kQ+ddJewMqp3YAZ0BnWu5vT5KqfBU5R7Q7FIE/kQ6ftBaxvDMDSikevHibUfYqFvGNe3auXUJSVNwzyRD500l7A7o1h/wtn8cVvnbNt+UvptnfHkGOPn5yIa4WMtVnZQL+BQt5YaVwWZNLVC0soiXxop72Aye6Nob6oqF/nZGq3KRbyOHl+zjGd5tTeoFEcC5/scCRP5INTvtQtj8rWAr3B6FsapXtNjEZZIRMEgzyRD3Y5Vbc8aqlcYfveHrGgisenZtDn0HGyUaVaCzQxHwWma4h8aLeZ1OTxC6yU6RFmd06/Ja3W1sJJpGgaMcgT+eQ3p1oqV5iq6WFmewmndhQmM32TdJBnuoYyI4w6dz/HMEdw1JsWVfH2xH04vGf7SrWMkzSkbziSp0xw69ke5kjLa/k6dT9zst2rQ6gp6fQNR/KUCUG20fPD/JTANE1va5xsb1wH4UdS1TccyVMmdFLn7pdXh0HqDTmRpkVLnXxqi6o/jRuO5CkTOqlz94spmt6XN3L4yme2+driz1zRaqfgcHuUGOQpE9qtc/eLlTS9za3tgNvAwanaMonGokzXUCaEvWnyE6VzeO7Vi4n80VI8BMBbE/c53u+2xd/jUzO2z/lJAj2LGOQpM9qpcz/00iwuX73xB2nWRBcLeWz4mTxOvfl+dCdKqWDk3Fe4ug0cnCpuomon7IZBnqhBqVzB/m+eRX2heYhuflep1pieyYjrC94f05wGDtzImyhlzA2zGcApDGGnB4NgkKfMYwkk2Qm6sUtSrYWtWF1DmccSSLIy+gQH79+S9GmEgkGeMi+JBSqULAHQb9iHv7zRh8mHt6ViFB4GBnnKpMZmZX76hFNvObxnOwZuvsn2vlp9EZPHL6SmH3xQzMlT5lhz8H77hFPv8JqDaWwoBqRjArVToQR5EfmvAD4F4Meq+rHl29YAmAKwAcDbAD6jqpfDOB5Rp0rlCr7w/FkG9oyr1RdW+sK7PebQS7P4oL4YeffSKIWVrvlTAPdabhsH8Iqq3gHgleXviRJjjuAZ4Anw9wnu8tV6pN1L4xDKSF5V/0pENlhufgDALy1//TUA/wPAvw3jeEROzHp3u4/WrKKhsHTTZH2UE68fUdX3AGD5/z9r9yAReUxEpkVkem5uLsLToV7X2N+7caMGcwKNC53IjXX6PW/kHGvlk2hP0KnEJ15V9RkAzwDAyMgIP0dTx6LeGIS6m9eerGZvosZPgUDrJG1S7Qk6FWWQ/zsR+aiqviciHwXw4wiPReS6Mcihl2ZjPhtKGzOIA/af6oqFPE6N77J9buaraxwcBfA5ABPL//92hMeijCuVK+hzqJZQoKmjJGXXpWoNh/dsb2t0npb2BJ0Kq4Ty61iaZL1VRN4F8GUsBffnReS3AFwE8HAYx6L0cJvkjPs8WDVDfqwt5FPVPCwOYVXXPOJw1yfCeH1KH+uCoiTrh1k1Q36Zo/VuH523I/GJV+pObpOcfv942vkk4PbYbipno2RlJbA3Ek3RR9yRkRGdnp5O+jTIh43jx2wrFby2TDPZtffNG7mWvTRL5QoOHp1F1bJtWuNOTe9fuYZafbGzH4QyRYCeTM+IyBlVHbG7jw3KqCNumxj74afc0XwjsAZ4oHmnJgZ48stu/USvY5CnjuzfvQl5I9d0Wzv1w27ljibm2ikqWVo/wSBPHRkbLuLpB7eiWMhDsJQ2saZa3Pj5JMBcO0UpK79fnHiljgWpUPCz0XGh32B9O0Wmm1oTBMEgT4lwq1UulSs49NIsAzxFpttaEwTBIE+JsfskwE21KSo5ESyq9mR1jRsGeUqEte595+ZBnDw/x06RFAm78tysYJCn2Nmtln329MWEz4p6VU4kswEeYHUNJYClkRSnRdXMBniAQZ4SkJXSNYpeTgR7dwy1rNlolJUqGidM11DkrPl3lkZSWBZV8eTYVoysX2Pb/gIArlybR6lcyexonkGeImWXfycKizlKNyu17Mpvq7V6Yh1S04DpGorUwaOzzL9TZKy17mPDRfSvbh27ZqmNgRWDPEWmVK7YfnwmCsNAv2E7MvfTFylLGOQpEqVyBV94/mzSp0E9Km/k8OVPb7G9L2iH1F7DnDyFonFy9Za8gSvX57kdH4Xq5tU5XL2+4Lli1U9fpCxhkKfArJOrTNFQFAr9qzH7+7s8H5e1PVy9MMhTYFzcRHFoJ6eepT1cvTAnT4FldUKL4qUARidOZGZHp7BwJE8dM/PwzLxTXMyt+4Bs1rx3giN5ArAUsEcnTmDj+DFfoyUzD8/FTRQ2AbB3xxCKDtUwWa557wRH8mS7KtVrtMQ8PEVBADy6YwhPjm0FAGwcP2b7SZEpQv8Y5DPE2kPGrDiwC9jmaMkpyHMET2Er5A0cvH/Lyu9cqVxBn4htKW5Wa947wSCfEW6j9XZWCJpvFERBCdA0Sr82v7jytfn7ahfgs1zz3gnm5DPCbbTud4Ug8/AUhryRw0C/0ZKGqdUXcOilWQDO6cCsbwDSCQb5jHAbre/fvamlH7fdaIl5eApqoN/A0w9uRdWh1fTlq3WUyhXH39esbwDSCQb5jHAbrY8NF/H0g1tRLOQhAIqFvO1oiZNd1KlC3sBX92xH+Uv3YGy46JpTb+fTJXljTj4jvPp5+FkhuLaQZ6qGOtI4oQos/T7um5qxfaz5O2bN2TMX3xkG+Yxop5+HOblaqdaQW65uKBby2Ll5kBtuU0fsKrWsQdxKGx5TzHj/mSBEU9QpcGRkRKenp5M+jUyzVuEQhaVYyDd1Ka0v+Is9xUIep8a9G5NlmYicUdURu/s4kqcmnFylKAhupGHa7VLKuaBgOPFKK0rlCnPuFIkg+QJOtgbDkXyPclrd6vb4/S9wJycKl1fevdFAv4EP6ovc7CNkHMn3oMZFS4obq1vdmo5NHr+A+mJ65meoOxk5QSFvrJTiHt6z3bHRWCNzOz8/pbzUHo7ke1AnvWiY96SgciKY/PVttr9j1sl8o0/w4Q+tQvVqveWTJoN6uCIP8iJyL4A/BJAD8CeqOhH1MbOuk93qWQNPQTmtRuV2fMmKNMiLSA7AHwH4JIB3AXxPRI6q6g+iPG7WOQVsuwmsxpp4oiDWFvKOc0Hcji85Uefk7wbwhqr+UFWvA/gGgAciPmbm+e1Fw4ZjFBYBsOFn8m3PBVH0og7yRQDvNHz/7vJtFCG/vWicauIH+g3cvDrXcjuREwXw3Tffd5wLouREnZMXm9uaSjhE5DEAjwHA0NBQxKeTHX4+Hjvl6C87dAgkcuNUm8VJ/WRFPZJ/F8C6hu9vA3Cp8QGq+oyqjqjqyODgYMSnQyZz1x2iqHExU7KiDvLfA3CHiGwUkdUAPgvgaMTHJA9uu+4Q2TH6xFcKzzps4GKm5EUa5FV1HsBvAzgO4HUAz6vqbJTHJG/sT0PtGOg3MPnwNjz1a1tbJvQb5Y0cHt0xxMVMKRN5nbyq/jmAP4/6OOSN5ZLkR2O3SBGgerWOyeMXcOXavOPggK2A04srXruc3x41Zm8ati4gL6fGd9lu/O5Elp9D6cQg38Xs/hAPHDkHoHVp+MGjswzw5MnMu7eT0uPEarqxQVkXc+tRY9VuD2/KJiO3FBL8lj1yYjX9GOS7WCc9aojcVGt1jE6cwC15w/b+gX6jaWL1obuKmDx+ARvHj2F04gRXt6YQ0zVdrJ0eNTet6sO1+cU4Tou6XKVag5ETGH3SlOIz2wGbqcB20oWUHI7ku0CpXMHoxImW0ZLfHjVPlM4xwFNb6guKD39olWs5ZDvpQkoOR/Ip52e05FRdw5JJCqJ6tY7yl+5xvJ/pwu7AkXzKdTpaMksmGeCpU15VM073s9omXTiSTzm30ZLTKP+F6Ys49eb7cZ4m9Rg/VTP7d29q2fGJ1Tbpw5F8yrmNlpxG+Qzw1Chv5LB3x1DL/I05uWo10G/4akfgt6U1JYsj+ZRzGy09PjWT4JlRWu3dMYST5+da5mlG1q9pmb8Bgm3Lxx2f0k80RZ0IR0ZGdHp6OunTSB2n1gWjEyeYcydb7CWTLSJyRlVH7O7jSD5GdsEasB9J+elJs3PzIJ47fdFxswbKLtask4kj+ZhYJ0mBpR7dkKWaZFPeyOGhu4p48UylJUXTmO+0ez0iq2Ihz+ZhGeA2kufEa0zsJknri9oU4IGlidOvv/qOZ9kke8KTH6xZJwb5mLTzx+a0Y1Pja/CPl/xgzToxyMeknT+2nMPeq42v4dRAisjEmnUCGORjY9dnxugTGLnmgJ43cnjk4+s8e9IwVZNtdjXuRp9goN9gzTo1YXVNTJz6zNjd5lTTbL4GG45lmwgw+evbAASrcadsYHVNl2gsqUzPvxgl4at7tjOYUxPWyXcJp9p4lktmg2Bp3mXn5kE8e/qi4+MY4KkdDPIp4dZSmOWS2fDWxH0rX588P2e7mrnIahlqEydeU8KtpTBbF/Q+a/D2uyEMkRcG+ZRwqnuvVGuwL6ikXlKp1pp2/WKHRwoL0zUp4bRfa07EcXEU9RZrvxl2eKQwcCSfEk4fzxngs4V7pFLYOJJPCWsd/S15AyJc9JRFbFlBYeJIPkXGhos4Nb4Lh/dsx7X5RVy+Wk/6lCgB7DdDYWKQT6FDL81yBJ9RrKChsDHIp0ypXOEIPgMKeWOlbNJsSMcKGooCc/IJcVrdykm3bPhJrY6ZL9+T9GlQBjDIJ8BtdSsn3bKBeXeKC9M1CXBb3co//u6RN9z/fPJGDnt3DHHlKiWKQT4mpXIFoxMnsHH8mGObgkvVGv/4u0itvojR29e0BHHTTav6MLJ+DVeuUqKYrumQU07d6bF+ukiuLeQxNlzEvqmZKE6ZInD6h5fxlc9sW+kxJMBKK+hqrY4DR87h6Qe3cjNtSgxH8h0wg3Zlube7mVM3+45Y+ekiKVha9er0GpROC6or6xuKhXxLr3+uYKWkMch3wC2nbsfPZKoZHPa/cDbo6VGMGvfjdfp35mQ6JYnpmg64/THbpXGcmo9ZMU3TfR75+LqVr53+nTmZTkkKNJIXkYdFZFZEFkVkxHLfARF5Q0QuiMjuYKeZLk5/tIV+wzaNs3PzoOPkHHWHXJ9gdcOm6wJg744hPDm2deU29oCnNAqarvlbAA8C+KvGG0XkTgCfBbAFwL0A/lhEeibKOf0xq7Y2FKvVF3DstfdWKiyoOy0sKq4v3Mi4f8jIYWT9mqbHsAc8pVGgdI2qvg4AIi3bWjwA4Buqeg3AWyLyBoC7Afx1kOOlhbVjpJmWedwh3WK2Kdi/exP2f/Ms6gtsH9ztzDkYawBnD3hKm6hy8kUApxu+f3f5thYi8hiAxwBgaGgootMJn90fs9tWffumZtAnwCLje8/ghCp1A890jYj8pYj8rc1/D7g9zeY22/Cmqs+o6oiqjgwODvo971Tyyr0ywKdPkBQaJ1SpG3gGeVX9ZVX9mM1/33Z52rsA1jV8fxuAS0FPNu3Ghoso5I2kT4N8yonYzq9Y9QEwcs3jFk6oUreIqk7+KIDPishNIrIRwB0A/iaiY6XKwfu3sJKmSzzy8XUtk6W51vklLAK4efUqTqhSVwqUkxeRXwPwHwAMAjgmIjOqultVZ0XkeQA/ADAP4POqmoldMBonZf3UxlNyzOqYxvmVjePHbB/L1sDUrQKN5FX1W6p6m6repKofUdXdDfc9paq3q+omVf1O8FPtHuYy9707hmwnJygd7FYoO+XZmX+nbsW2BhF5onQOz52+aD/bbDHQb8Do49tB3OyqY7igiXoNg3wESuWK7wAPAKrAnrvXreR8KR52o3MuaKJew941ISiVKzj00uzKoqfGdrN2rPXy1Vodz52+iF+8fSlHzFx+ePoE+I2PD+HFM5Wm1chuo3MuaKJewiAfUKlcaVnF6hbgzbpsayBXAKfefD+CM8w2VeDJsa0YWb/Gd/9/ol7CIB/Q5PELvtsUmD3jndofUPjMlAxH55RVzMkH5HdpuwB4dMcQxoaLbVdqFAt5z/1Es8z8dGSdz+CEKRGDfGBeAVsAFPIGCv0Gnjt9EaMTJ7Bz86DvCdaBfgOnxnfh6Qd/ITMVOO38lMVCHqfGd+HtiftweM92TpgSWTBdE9D+3ZtcN/t4dMdQU6VNpVrDi2cq+MXb1+C7b77vWYHzDx/Mo1SurASrXt5YxAzYpXIFjz8/A/W4ONaROlMyRK04kg/IrV9NIW/YllLW6gv4wXs/xeE92zHQ797rpr6oK4t2xoaL+Oqe7T07ot+5eRCjEyfw+JR3gOdIncgfBvkQ2PWryRs5iDhX2pjlluUv3YPR29c4PGpJY95/bLiIyYe32fZY6WY3r87hxTOVlV21nBTyBt6euA+nxncxwBP5wCAfAqcFNNXlQO5k8vgFlMoVfNejdNKa9x8bLmLRa6jbRfJGDkaur2VXLbvHHbx/C0rlCkYnTmDj+DGMTpxAqVyJ6UyJug9z8h2y27D71Piupsd4NSm7VK1h8vgFz7z8zs03+uybx01jiC/kDVy5Pu+rpNRcMFb02FXLfKx5jQHgwJFzK28I5j66ADiyJ7LBIN+BUrniK9Ds372p6XFWfSK+VreePD9ne9wwBdm1yugTTD68DWPDxZU3Ibefq2izGMnpOeZkrGl04oTtPrp2W/EREdM1HZk8fsEx0DQaGy7iobucA8+Cqq9yQTMnb3fcRnmjD7kOJ2UD7VrVcEizA6fTjktm0LYGZL+NwZzWJXArPiJ7DPIdcAoolWqtJT9sjsKdKLzrws2cvNNxBcDbE/fh9X//K/jKw9tW5ga8KnfCUl/Qlje4drs5Wuc1BvoN3LSqD49PzTTl3dkKmKg9TNd0YG0h75iOsKZt/Iwwzdx0pVpraW5m5ARXrs1j4/gx9IlgwWbCtTHAWWvFnyidw7OnL3r/UAFZf87GzVP89osxz90tHWaXAuPKViJnDPIdcMu1W/PDbm8Ipsa8c+OEbqHfwD98MI9qbalKxy7AewW4kfVrMPU376DeYT6m6OP8Aee2vZ3kyd3SYeZ1YrMxIn8Y5Dvgtfq0cVTrNfnqtmpzdOLESj19o5wIFlV9BbjJ4xdsA7z5Gl4dM0+N78LoxAnXQB/2SNor786VrUT+MSffobHhouPkojV9Ys01F/KGZ3+VUrniGFgXVfGWzwVBTgHTfA23vL0ZuO3y6+Y8QhQrT5l3JwoPR/IB2I3SBc117UD7I09z60An7QQ7p3SR+Rpf/vSWln74ALB3uWMm0Fl+PQjm3YnC0xNB3m5hUhwf58eGi5j+0ftN/WkUwItnKhhZv6ajc/DaOtAu2Ln9/E4B0+wTc6lawy15AyJA9Wrd8frFmSKJ+02FqJd1fZD3uzApKifPz9k2IOt0cY7XalZrasTr57cLmDs3DzZth1et1ZE3cji8Z3tqAinz7kTh6PqcvN+FSVEJe3GO2/OKhXxL4PPz85sLlMw8/snzc4leMyKKT9cH+aRXQIY9Sej0PHPrQKtOfv6krxkRxafrg3yclRh23Q/bXdnpxamS5dGGidBGnfz8rF4hyo6uD/JhB1knZu7b7HfemPu2azPcaT7Zrm3x4T3b8eTYVtvHd/Lzx3XNiCh5oinqSz4yMqLT09NtPy+O6hqnBUHWLolJ6OTnT6oiiYjCJyJnVHXE9r5eCPJx2Dh+zLbqRQC8NXFf3KdDRLTCLch3fbomLsxjE1E3YpD3Kew8NrewI6I4dP1iqLiEuQoz6QVcRJQdDPJt8FqF6Xcy020BE4M8EYWJQT4k7YzOuRiJiOLCnHxI2mmvwElcIooLg3xI2hmdczESEcWFQT4k7YzO7Va1hr3xBhERwJx8aNrd6IKtdIkoDgzyIeFGF0SURoGCvIhMAvg0gOsA3gTwz1W1unzfAQC/BWABwL9S1eMBzzX1ODonorQJmpP/CwAfU9VfAPC/ABwAABG5E8BnAWwBcC+APxaRnOOrEBFRJAIFeVV9WVXnl789DeC25a8fAFYD7fwAAANUSURBVPANVb2mqm8BeAPA3UGORURE7QuzuuZfAPjO8tdFAO803Pfu8m0tROQxEZkWkem5ubkQT4eIiDxz8iLylwB+zuauL6rqt5cf80UA8wCeM59m83jbnsaq+gyAZ4ClVsM+zpmIiHzyDPKq+stu94vI5wB8CsAn9EZz+ncBrGt42G0ALnV6kkRE1JlAm4aIyL0A/gDAP1PVuYbbtwD4b1jKw68F8AqAO1R1wfaFbjxvDsCPOj6hZNwK4O+TPomU4LVoxutxA69Fs7Cvx3pVHbS7I2iQfwPATQD+7/JNp1X1Xy7f90Us5ennAexT1e/Yv0p3E5Fppx1ZsobXohmvxw28Fs3ivB6B6uRV9Z+43PcUgKeCvD4REQXD3jVERD2MQT64Z5I+gRThtWjG63EDr0Wz2K5HoJw8ERGlG0fyREQ9jEGeiKiHMciHSER+V0RURG5N+lySIiKTInJeRF4TkW+JSCHpc4qbiNwrIhdE5A0RGU/6fJIkIutE5KSIvC4isyLyO0mfU9JEJCciZRH573Ecj0E+JCKyDsAnAVxM+lwSZtuZNCuWu63+EYBfAXAngEeWu7Jm1TyAL6jqzwPYAeDzGb8eAPA7AF6P62AM8uE5DODfwKFHT1a4dCbNirsBvKGqP1TV6wC+gaWurJmkqu+p6veXv/4ploJbZjddEJHbANwH4E/iOiaDfAhE5H4AFVU9m/S5pExjZ9Ks8N2BNWtEZAOAYQCvJnsmifoqlgaDi3EdkNv/+eTWjRPA7wG4J94zSk6HnUmzwncH1iwRkQ8DeBFLLU7+X9LnkwQR+RSAH6vqGRH5pbiOyyDvk1M3ThHZCmAjgLMiAiylJ74vIner6v+J8RRj02Fn0qxgB1YLETGwFOCfU9UjSZ9PgkYB3C8ivwrgQwD+sYg8q6p7ozwoF0OFTETeBjCiqpnsuOfUmTQrRGQVliacPwGgAuB7AH5DVWcTPbGEyNLI52sA3lfVfUmfT1osj+R/V1U/FfWxmJOnsP1HAP8IwF+IyIyI/KekTyhOy5POvw3gOJYmGZ/PaoBfNgrgNwHsWv59mFkeyVJMOJInIuphHMkTEfUwBnkioh7GIE9E1MMY5ImIehiDPBFRD2OQJyLqYQzyREQ97P8DuINzEG9m0y8AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(x, y)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 批量梯度下降法(Stochastic Gradient Descent)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def J(theta, X_b, y):\n",
    "    try:\n",
    "        return np.sum((y - X_b.dot(theta)) ** 2) / len(y)\n",
    "    except:\n",
    "        return float('inf')\n",
    "    \n",
    "def dJ(theta, X_b, y):\n",
    "    return X_b.T.dot(X_b.dot(theta) - y) * 2. / len(y)\n",
    "\n",
    "def fit_gd(X_b, y, initial_theta, eta, n_iters=1e4, epsilon=1e-8):\n",
    "\n",
    "    theta = initial_theta\n",
    "    cur_iter = 0\n",
    "\n",
    "    while cur_iter < n_iters:\n",
    "        gradient = dJ(theta, X_b, y)\n",
    "        last_theta = theta\n",
    "        theta = theta - eta * gradient\n",
    "        if (abs(J(theta, X_b, y) - J(last_theta, X_b, y)) < epsilon):\n",
    "            break\n",
    "\n",
    "        cur_iter += 1\n",
    "\n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 933 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X_b.shape[1])\n",
    "eta = 0.01\n",
    "theta = fit_gd(X_b, y, initial_theta, eta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([3.01400049, 3.98951984])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 随机梯度下降法\n",
    ">无需指定学习率，每次迭代时计算一个随机点，通过方法计算得到学习率.**可以大大提高训练速度**\n",
    "![随机梯度下降法方程推导](images/随机梯度下降法方程推导.jpg)\n",
    "![随机梯度下降法中η的取值](images/随机梯度下降法中η的取值.png)\n",
    "> 上面η的变化过程实际就是`模拟退火`的思想\n",
    "![模拟退火的表达式](images/模拟退火的表达式.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dJ_sgd(theta, X_b_i, y_i): # 随机梯度下降法的变化率表达式，这里只取一个点，下面会迭代多次来实现收敛的目的\n",
    "    return 2 * X_b_i.T.dot(X_b_i.dot(theta) - y_i) * 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fit_sgd(X_b, y, initial_theta, n_iters): # 和上一节的fit_gd进行比较\n",
    "    # 下面是两个经验值，仅供参考\n",
    "    t0 = 5\n",
    "    t1 = 50\n",
    "    \n",
    "    def learning_rate(t): # 这里的学习率不能用固定的η了\n",
    "        return t0 / (t + t1)\n",
    "    \n",
    "    theta = initial_theta\n",
    "    for cur_iter in range(n_iters):\n",
    "        rand_i = np.random.randint(len(X_b))\n",
    "        gradient = dJ_sgd(theta, X_b[rand_i], y[rand_i])\n",
    "        theta = theta - learning_rate(cur_iter) * gradient\n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 207 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X_b.shape[1])\n",
    "theta = fit_sgd(X_b, y, initial_theta, n_iters=m//3) # 耗时相对于fit_gd大幅降低，准确率却几乎差不多，可以看到随机梯度下降法的威力了，所以在对训练时间要求高地场景强烈推荐随机梯度下降法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2.94240975, 3.90353915])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
